#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MVNum 100
typedef enum{FALSE, TRUE} Boolean;

typedef char VerTexType;
typedef int ArcType;

typedef struct
{
    VerTexType vexs[MVNum];//顶点表
    ArcType arcs[MVNum][MVNum];//邻接矩阵
    int vexnum, arcnum;//图的当前点数和边数
} MGraph;

//查找顶点在顶点表中的位置
int locate_vertex(MGraph *G, char vertex_name)
{
    for (int i = 0; i < G->vexnum; i++)
    {
        if (G->vexs[i] == vertex_name)
        {
            return i;
        }
    }
    return -1;
}

//建立邻接矩阵
void create_graph(MGraph **G_pp, char *graph_data_filename)
{
    FILE *fp = fopen(graph_data_filename, "r");
    if (fp == NULL)
    {
        printf("Error in opening file %s\n", graph_data_filename);
        exit(EXIT_FAILURE);
    }

    //分配图结构内存
    *G_pp = (MGraph *)malloc(sizeof(MGraph));
    if (*G_pp == NULL)
    {
        printf("Memory allocation failed");
        fclose(fp);
        exit(EXIT_FAILURE);
    }
    MGraph *G = *G_pp;

    //读取顶点数和边数
    if (fscanf(fp, "%d %d", &G->vexnum, &G->arcnum) != 2)
    {
        printf("Error reading vertex and edge numbers\n");
        fclose(fp);
        free(G);
        exit(EXIT_FAILURE);
    }

    //检查顶点数和边数是否合法
    if (G->vexnum <= 0 || G->vexnum > MVNum || G->arcnum < 0 || G->arcnum > MVNum * MVNum)
    {
        printf("Invalid vertex or edge count\n");
        fclose(fp);
        free(G);
        exit(EXIT_FAILURE);
    }
    //读取顶点名字
    for (int i = 0; i < G->vexnum; i++)
    {
        if (fscanf(fp, " %c", &G->vexs[i]) != 1)
        {
            printf("Error reading vertex name\n");
            fclose(fp);
            free(G);
            exit(EXIT_FAILURE);
        }
    }


    //初始化邻接矩阵
    memset(G->arcs, 0, sizeof(G->arcs));

    //读取边信息并填充邻接矩阵
    char v1, v2;
    for (int i = 0; i < G->arcnum; i++)
    {
        if (fscanf(fp, " %c %c", &v1, &v2) != 2){
            printf("Error reading edge information\n");
            fclose(fp);
            free(G);
            exit(EXIT_FAILURE);
        }
        int pos1 = locate_vertex(G, v1);
        int pos2 = locate_vertex(G, v2);
        if (pos1 == -1 && pos2 == -1)
        {
            printf("Invalid vertex in edge: %c %c\n", v1, v2);
            fclose(fp);
            free(G);
            exit(EXIT_FAILURE);
        }
        G->arcs[pos1][pos2] = 1;
        G->arcs[pos2][pos1] = 1;//无向图对称
    }

    fclose(fp);
}

//DFS(递归实现)
void dft(MGraph *G, int i, Boolean visited[], char *result_sequence, int *visited_order)
{
    if (i < 0 || i >= G->vexnum || visited[i])
    {
        return;
    }

    visited[i] = TRUE;
    result_sequence[(*visited_order)++] = G->vexs[i];

    for (int j = 0; j < G->vexnum; j++)
    {
        if (G->arcs[i][j] == 1 && !visited[j])
        {
            dft(G, j, visited, result_sequence, visited_order);
        }
    }
}

//BFS(使用队列)
void bft(MGraph *G, int k, Boolean visited[], char *visited_sequence)
{
    int queue[MVNum];
    int front = 0, rear = 0;
    int order = 0;

    if (k < 0 || k >= G->vexnum || visited[k])
    {
        return;
    }

    visited[k] = TRUE;
    visited_sequence[order++] = G->vexs[k];
    queue[rear++] = k;

    while (front != rear)
    {
        int current = queue[front++];
        for (int j = 0; j < G->vexnum; j++)
        {
            if (G->arcs[current][j] == 1 && !visited[j])
            {
                visited[j] = TRUE;
                visited_sequence[order++] = G->vexs[j];
                queue[rear++] = j;
            }
        }
    }
}

int main()
{
    MGraph *G = NULL;
    Boolean visited[MVNum];
    char dft_sequence[MVNum] = {'\0'};
    char bft_sequence1[MVNum] = {'\0'};
    char bft_sequence2[MVNum] = {'\0'};
    int visited_order = 0;

    //建立邻接矩阵
    create_graph(&G,"E:/wangshiyugit/lab6/graph_data.txt");

    //DFS
    memset(visited, FALSE, sizeof(visited));
    dft(G, 0 , visited, dft_sequence, &visited_order);
    printf("dft_sequence: %s\n", dft_sequence);

    //BFS1
    memset(visited, FALSE, sizeof(visited));
    bft(G, 0, visited, bft_sequence1);
    printf("bft_sequence(from 0): %s\n", bft_sequence1);

    //BFS2
    memset(visited, FALSE, sizeof(visited));
    bft(G, 3, visited, bft_sequence2);
    printf("bft_sequence(from 3): %s\n", bft_sequence2);

    free(G);//释放图内存
    return 0;
}